package com.honeywen.mymvc.leetcode;


/**
 * 25. k个一组翻转链表
 * https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
 *
 * @author wangwei
 * @date 2019/5/8
 */
public class ReverseKGroup {


    private static void print(ListNode node) {
        System.out.println();
        while (node != null) {
            System.out.print(node.val + "->");
            node = node.next;
        }
        System.out.println();
    }

    public static ListNode reverseKGroup(ListNode head, int k) {


        ListNode node = head;
        ListNode fake = new ListNode(0);
        fake.next = head;

        //  上一段的尾巴
        ListNode tail = fake;
        while (node != null) {
            if (!checked(node, k)) {
                // 到尾巴了
                tail.next = node;

                break;
            }

            ListNode prev = null;
            ListNode first = node;
            for (int i = 0; i < k; i++) {
                ListNode oldnext = node.next;
                // 改变指向
                node.next = prev;

                // prev前进， node前进
                prev = node;
                node = oldnext;

            }
            // 头，尾
            // 新的， 这一段结尾是prev , 下一段开头是 node,
            tail.next = prev;

            // 重置tail为转换后的新尾巴
            tail = first;


        }


        return fake.next;
    }

    private static boolean checked(ListNode node, int k) {

        for (int i = 0; i < k; i++) {
            if (node == null) {
                return false;
            }
            node = node.next;
        }

        return true;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        print(n1);

//        print(reverseKGroup(n1, 2));
        print(reverseKGroup(n1, 3));
    }

}
